/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: LIUYANJIAO
 * Date: 2024-12-12
 * Time: 20:18
 */
public class Main {
    public static String longestPalindrome(String s) {
        if (s == null || s.length() < 1) return "";
        int start = 0, end = 0;
        char[] b = s.toCharArray();
        boolean[][] dp = new boolean[b.length][b.length];

        // 初始化对角线，每个字符都是一个长度为1的回文
        for (int i = 0; i < b.length; i++) {
            dp[i][i] = true;
        }

        // 动态规划填表
        for (int i = b.length - 1; i >= 0; i--) {
            for (int j = i + 1; j < b.length; j++) {
                if (b[i] == b[j]) {
                    // 当长度为2或者dp[i+1][j-1]为true时，子串[i, j]是回文
                    dp[i][j] = (j - i == 1) || dp[i + 1][j - 1];
                    // 更新最长回文子串的起始和结束位置
                    if (dp[i][j] && j - i > end - start) {
                        start = i;
                        end = j;
                    }
                } else {
                    dp[i][j] = false;
                }
            }
        }
        // 返回最长回文子串
        return s.substring(start, end + 1);
    }

    public static void main(String[] args) {
        String s = "babab";
        System.out.println(longestPalindrome(s));
    }

    public int waysToStep(int n) {
        int[]bp=new int[n+1];
        bp[0]=1;
        bp[1]=1;
        bp[2]=2;
        for (int i = 3; i < n+1; i++) {
            bp[i]=bp[i-1]+bp[i-2]+bp[i-3];
        }
        return bp[n];
    }
}